package j2024.j202409;

public class j0902 {
    /**
     * 509. 斐波那契数
     */
    int[] memo;
    public int fib(int n) {
        memo = new int[31];
        for(int i = 0;i < 31;i++){
            memo[i] = -1;
        }
        return dfs(n);
    }
    public int dfs(int n){
        if(memo[n]!=-1){
            return memo[n];
        }
        if(n==0 || n==1){
            memo[n] = n;
            return n;
        }
        memo[n]  = dfs(n-1)+dfs(n-2);
        return memo[n];
    }
}
